#include<vector>
using std::vector;


class Solution {
private:
    vector<vector<int>> edges;
    vector<int> visited;

public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        visited.resize(numCourses, false);
        edges.resize(numCourses);
        // 构建图
        for (auto& v: prerequisites) {
            edges[v[0]].push_back(v[1]);
        }
        for (int u = 0; u < numCourses; u++) {
            if (!visited[u]) {
                visited[u] = 1;
                if (!dfs(u)) return false;
            }
        }
        return true;

    }

    bool dfs(int u) {
        visited[u] = 1; // 代表该次循环访问启动的节点
        for (auto& v: edges[u]) {
            if (visited[v] == 0) {
                if (!dfs(v)) return false;
            }
            else if (visited[v] == 1) return false;
            else {
                // 已经被其它节点启动过了，从该点搜索没有环

            }
        }
        visited[u] = 2;
        return true;
    }
};